#ifndef ARVOREC_H_
#define ARVOREC_H_
#include <cstdlib>
#include <iostream>
#include <vector>
#include <iomanip>
#include <exception>

using namespace std;


template<class TCHV, class TDADO>
struct NoC
{
	TCHV Chave;
	vector<TDADO> Valor;
	NoC<TCHV,TDADO> *esq, *dir;

	NoC()
	{
		esq = dir = NULL;
	}

	NoC(TCHV c, TDADO v, NoC<TCHV, TDADO> *e = NULL, NoC<TCHV, TDADO> *d = NULL)
	{
		Chave = c;
		Valor.push_back(v);
		esq = e;
		dir = d;
	}

};

template<class TCHV, class TDADO>
class ArvoreC
{
private:
	NoC<TCHV, TDADO> *raiz;

public:

	ArvoreC()
	{
		raiz = NULL;
	}

	virtual ~ArvoreC()
	{
		NoC<TCHV,TDADO> *tmp = raiz;
		while(tmp != NULL)
		{
			tmp = Remover(tmp->Chave, tmp);
		}
	}

	bool Vazia()
	{
		return raiz == NULL;
	}

private:

	NoC<TCHV, TDADO> *Insere(TCHV chv, TDADO dado, NoC<TCHV,TDADO> *sub)
	{

	  if ( sub == NULL )
	  {
	    sub = new NoC<TCHV, TDADO>( chv, dado );
	  }
	  else
	  {

	    if ( chv < sub->Chave )
	       sub->esq = Insere( chv, dado, sub->esq );

	    if ( chv > sub->Chave )
	        sub->dir = Insere( chv, dado, sub->dir );

	    if (chv == sub->Chave)
			sub->Valor.push_back(dado);

	    }

	  return sub;

	}

	NoC<TCHV,TDADO> * Localizar( TCHV chv, NoC<TCHV,TDADO> * subarv )
	{
	  if ( subarv == NULL ) return NULL;
	  else
	  {
	    if ( chv < subarv->Chave )
	      return Localizar( chv, subarv->esq );
	    else
	    {
	      if ( chv > subarv->Chave )
	        return Localizar( chv, subarv->dir );
	      else
	        return subarv; // No Encontrado
	    }
	  }
	}

	void Imprime( NoC<TCHV,TDADO> *subarv, int nv )
	{
	  if ( subarv == NULL ) return;
	  Imprime( subarv->dir, nv + 1 );
	  cout << setw(nv*5) << " " << subarv->Chave << endl;
	  Imprime( subarv->esq, nv + 1 );
	}

	NoC<TCHV,TDADO> *LocalizarMin( NoC<TCHV,TDADO> *subarv )
	{
		  if ( subarv->esq != NULL ) subarv = LocalizarMin( subarv->esq );
		  return subarv;

	}

	NoC<TCHV,TDADO> * Remover( TCHV chave, NoC<TCHV,TDADO> * subarv )
	{
	  NoC<TCHV,TDADO> * tmp, * filho;
	  if ( subarv == NULL )
	  {
	    return NULL;
	  }
	  else
	  {
	    if ( chave < subarv->Chave )
	    {
	      subarv->esq = Remover( chave, subarv->esq );
	    }
	    else
	    {
	      if ( chave > subarv->Chave )
	      {
	        subarv->dir = Remover( chave, subarv->dir );
	      }
	      else
	      {
	        if ( subarv->esq && subarv->dir )
	        {
	          tmp = LocalizarMin( subarv->dir );
	          subarv->Chave = tmp->Chave;
	          subarv->dir = Remover( subarv->Chave, subarv->dir );
	        }
	        else
	        {
	          tmp = subarv;
	          if ( subarv->esq == NULL ) filho = subarv->dir;
	          if ( subarv->dir == NULL ) filho = subarv->esq;
	          delete tmp;
	          return filho;
	        }
	      }
	    }
	  }
	  return subarv;
	}

	int Altura( NoC<TCHV,TDADO> * subarv )
	{
	  int ae, ad;
	  if ( subarv == NULL ) return 0;
	  if ( subarv->esq == NULL && subarv->dir == NULL ) return 1;
	  ae = Altura( subarv->esq );
	  ad = Altura( subarv->dir );
	  if ( ae > ad )
		return ae + 1;
	  else
	    return ad + 1;
	}

public:

	void Insere(TCHV chave, TDADO dado)
	{
		raiz = Insere(chave, dado, raiz);
	}

	vector<TDADO> Seleciona(TCHV chave)
	{

		vector<TDADO> valores;

		NoC<TCHV,TDADO> *tmp = Localizar(chave, raiz);

		if(tmp != NULL){
			valores = tmp->Valor;
		}

		return valores;

	}

	void Imprime()
	{
		Imprime(raiz,1);
	}

	void Remove(TCHV chave)
	{
		raiz = Remover(chave, raiz);
	}

	void Altura()
	{
		return Altura(raiz);
	}

};

#endif /*ARVOREC_H_*/
